// 插入排序 
// 假定左侧为已排序区域，根据索引递增 选择元素
// 将选择的元素跟左侧已排序区域进行比较排序

function Insertion(arr) {
	const len = arr.length;
	if (len <= 1) return arr;

	for (let i = 1; i < len; i++) {
		for (let j = i; j > 0 && (arr[j - 1] > arr[j]); j--) {
			const tmp = arr[j]
			arr[j] = arr[j - 1]
			arr[j - 1] = tmp;
		}
	}
	return arr;
}

module.exports = Insertion